Trần Công Minh được gọi vào đội tuyển quốc gia lần đầu tiên vào năm 1995 để chuẩn bị cho SEA Games 18. Tại Sea Games này, ông chia sẻ vị trí hậu vệ phải với hậu vệ Nguyễn Chí Bảo (Công an TP.HCM). Trong trận đấu cuối cùng của vòng bảng gặp Indonesia, chính nỗ lực dốc bóng lăn xả của ông đã tạo cơ hội để tiền vệ Nguyễn Hữu Đang đệm bóng ghi bàn thắng quyết định của trận đấu, loại đội tuyển chủ nhà Indonesia, đồng thời đem lại chiếc vé vào bán kết cho đội tuyển Việt Nam.

Kể từ sau SEA Games 18, ông trở thành hậu vệ phải không thể thay thể trong đội tuyển Việt Nam. Với lối chơi công thủ toàn diện và tinh thần thi đấu cao độ, ông để lại ấn tượng sâu sắc trong lòng người hâm mộ.

Tại Tiger Cup 1996, Trần Công Minh là một trong những tuyển thủ thi đấu xuất sắc nhất. Ông đã ghi được 2 bàn thắng cho đội tuyển: một bàn trong trận thắng Campuchia 3-1 và một bàn thắng đáng nhớ trong trận thắng Myanmar 4-1.

Tại SEA Games 19, do chấn thương, ông đã không tham dự trận đấu đầu tiên gặp Malaysia. Thế vào chỗ của ông là cầu thủ Nguyễn Phúc Nguyên Chương. Đội tuyển Việt Nam đã để thua 0-1.

Tại Tiger Cup 1998, ông một lần nữa tỏa sáng trong vai trò hậu vệ phải. Trong trận đấu đầu tiên gặp Lào, ông đã kiến tạo 2 đường chuyền thành bàn cho đồng đội. Tuy nhiên, đội tuyển Việt Nam một lần nữa lỗi hẹn với chức vô địch.

Tại SEA Games 20, hàng phòng ngự của Việt Nam gồm Đỗ Khải, Mai Tiến Dũng, Phạm Như Thuần, Nguyễn Đức Thắng và Trần Công Minh được xem là hàng phòng ngự chắc chắn nhất giải. Cho đến trước trận chung kết, họ không để lọt lưới một bàn nào. Tuy nhiên, đội tuyển Việt Nam cũng chỉ giành được huy chương Bạc, sau khi thúc thủ 0-2 trước Thái Lan. Trần Công Minh giành được danh hiệu Quả bóng vàng năm đó.

Tiger Cup 2000 là giải đấu cuối cùng của Trần Công Minh cho đội tuyển Việt Nam. Mặc dù đã lớn tuổi nhưng ông vẫn làm tròn vai trò phòng ngự của mình. Tại giải đấu này, Việt Nam bị loại tại bán kết sau khi thua 2-3 trước Indonesia trong hiệp phụ.

Cũng trong năm 2000, trước khi Tiger Cup 2000 khởi tranh, Trần Công Minh được góp mặt trong đội hình những ngôi sao toàn châu Á trong trận đấu chia tay tuyển thủ người Iran Nader Mohammadkhani, sánh vai cũng với Dusit Chalermsan, Hong Myeong-bo, Lee Dong-gook, Tochtawan Sripan, Yoo Sang-chul và Atsuhiro Miura đối đầu với tuyển chủ nhà Iran. Iran thắng trận đấu này 5-0.